package sort.heapSort;

/**
 * @Author: zhang
 * @Description: 堆排序
 * @Date: Created in 18:21 2019/9/20
 */
public class heapSortTest {

    public static void main(String[] args) {
        int[] arrays = new int[]{5, 1, 7, 4, 8, 9, 2, 3, 6, 0};
        //sort.heapSort(arrays);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + " ");
        }
    }

    public static void heapSort(int[] a) {
        //将树调整为（大根堆），从最后一棵树开始调整
        for (int i = (a.length - 1 - 1) / 2; i >= 0; i--) {
            adjust(a, i, a.length - 1);
        }

        //整棵树调整的时间复杂度nlogn
        //开始排序--前后交换
        for (int j = 0; j < a.length - 1; j++) {
            int tmp = a[a.length - 1 - j];
            a[a.length - 1 - j] = a[0];
            a[0] = tmp;
            //交换后再调整(-1是因为交换的值是有序的)
            adjust(a, 0, a.length - 1 - j - 1);
        }

    }

    //一次调整的时间复杂度为logn
    public static void adjust(int[] a, int start, int end) {
        int tmp = a[start];
        for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {
            //找到左右孩子的最大值下标
            if (i < end && a[i] < a[i + 1]) {
                i++;    //此时i的位置就是左右孩子的最大值
            }
            //比较tmp与左右孩子最大值
            if (a[i] > tmp) {
                a[start] = a[i];
                start = i;
            } else {
                //从后向前调整，发现小于tmp没有必要调整
                break;
            }
        }
        //退出循环以后把tmp放入
        a[start] = tmp;
    }

}
